package com.bupt.basic;


import com.bupt.algorithm.DijkstraAlgorithm;
import com.bupt.annotation.MParam;
import com.bupt.exception.BaseException;
import com.bupt.utils.LocalVerify;
import org.springframework.lang.NonNull;

import java.util.*;
import java.util.stream.Collectors;

import static com.bupt.basic.BasicNetWork.*;

/**
 * 基础网络的相关操作 是一个工具类
 */
public final class BasicNetWorkUtil {
    private BasicNetWorkUtil() { /*refuse new obj*/}

    // 查看是否存在边信息
    public static boolean havePathOnNode(@NonNull String nodeId, @NonNull BasicNetWork netWork) {
        List<BasicLink> fiberLinks = netWork.getFiberLinks();
        if (null != fiberLinks && fiberLinks.size() > 0) {
            for (BasicLink link : fiberLinks) {
                // 存在邻边
                if (link.getNodeHead().equals(nodeId) || link.getNodeTail().equals(nodeId)) {
                    return true;
                }
            }
        }
        return false;
    }

    // 计算整个网络的平均最短路径长度 FIBER层的
    public static double calculateFiberAVGShortestPathLength(@MParam("当前网络信息") BasicNetWork netWork) throws BaseException {
        return calculateAVGShortestPathLength(netWork, LayerEnum.FIBER);
    }

    // 计算整个网络的平均最短路径长度
    public static double calculateAVGShortestPathLength(@MParam("当前网络信息") BasicNetWork netWork,
                                                        @MParam("层次信息") LayerEnum layer) throws BaseException {
        // 校验网络信息
       // netWork.checkCurrentNetWork();
        double res = 0.0;
        List<BasicNode> nodeList = netWork.getNodeList();
        int n = nodeList.size();// 阶数
        if (n > 1) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        List<String> list = calculatePathByDAlgorithm(netWork, nodeList.get(i).getNodeId(),
                                nodeList.get(j).getNodeId(), layer);
                        res += list.size() > 0 ? list.size() - 1 : 0;
                    }
                }
            }
        }
        if (n > 1) {
            return res / (n * (n - 1));
        } else {
            return 0;
        }

    }

    // 计算当前网络 FIBER层 的拓扑联通度
   /* public static int calculateFiberLevelNodeConnectivity(@MParam("当前网络信息") BasicNetWork netWork) throws BaseException {
        return calculateNodeConnectivity(netWork, LayerEnum.FIBER);
    }

    // 计算当前网络的拓扑联通度
    public static int calculateNodeConnectivity(@MParam("当前网络信息") BasicNetWork netWork,
                                                @MParam("层次信息") LayerEnum layer) throws BaseException {
        netWork.checkCurrentNetWork();
        Map<String, Integer> keyToIndexMap = new HashMap<String, Integer>();
        Map<Integer, String> indexToKeyMap = new HashMap<Integer, String>();
        // 生成当前的网络计算当前的聚集系数
        int[][] currentNetWorkMatrix = getCurrentNetWorkO1Matrix(netWork, layer, keyToIndexMap, indexToKeyMap,
                null);
        StoerWagnerAlgorithm algorithm = new StoerWagnerAlgorithm(currentNetWorkMatrix);
        return algorithm.stoer_wagner();
    }*/

   /* // 计算当前网络的Fiber层的聚集系数
    public static double calculateFiberConvergenceFactorByCurrentNetWork(@MParam("当前网络信息") BasicNetWork netWork)
            throws BaseException {
        return calculateConvergenceFactorByCurrentNetWork(netWork, LayerEnum.FIBER);
    }*/

  /*  // 计算当前网络的聚集系数
    public static double calculateConvergenceFactorByCurrentNetWork(@MParam("当前网络信息") BasicNetWork netWork,
                                                                    @MParam("层次信息") LayerEnum layer) throws BaseException {
        netWork.checkCurrentNetWork();
        Map<String, Integer> keyToIndexMap = new HashMap<String, Integer>();
        Map<Integer, String> indexToKeyMap = new HashMap<Integer, String>();
        // 生成当前的网络计算当前的聚集系数
        int[][] currentNetWorkMatrix = getCurrentNetWorkO1Matrix(netWork, layer, keyToIndexMap,
                indexToKeyMap, null);
        ConvergenceFactorAlgorithm algorithm = new ConvergenceFactorAlgorithm(currentNetWorkMatrix);
        return algorithm.getCF();
    }
*/
    // 判断任意两个节点之前是否存在 fiber 路径
    public static boolean haveFiberPathBetweenTowNode(@MParam("当前网络信息") BasicNetWork netWork,
                                                      @MParam("起始节点") String fromNodeId,
                                                      @MParam("终止节点") String toNodeId) throws BaseException {
        return havePathBetweenTowNode(netWork, fromNodeId, toNodeId, LayerEnum.FIBER);
    }

    // 判断任意两个节点之前是否存在 某一层的 路径
    public static boolean havePathBetweenTowNode(@MParam("当前网络信息") BasicNetWork netWork,
                                                 @MParam("起始节点") String fromNodeId,
                                                 @MParam("终止节点") String toNodeId,
                                                 @MParam("层次信息") LayerEnum layer) throws BaseException {
        //netWork.checkCurrentNetWork();
        List<String> list = calculateFiberPathByDAlgorithm(netWork, fromNodeId, toNodeId);
        if (null != list && list.size() > 0) return true;// 两个点之前存在路径
        return false;// 不存在路径的情况
    }

    // 计算fiber的最短路径 或者说是否存在最短的路径的问题
    public static List<String> calculateFiberPathByDAlgorithm(@MParam("当前网络信息") BasicNetWork netWork,
                                                              @MParam("起始节点") String fromNodeId,
                                                              @MParam("终止节点") String toNodeId) throws BaseException {
        return calculatePathByDAlgorithm(netWork, fromNodeId, toNodeId, LayerEnum.FIBER);
    }

    // 单单计算fiber 层次的
    public static List<BasicLink> calculateFiberLinkPathByDAlgorithm(@MParam("当前网络信息") BasicNetWork netWork,
                                                                     @MParam("起始节点") String fromNodeId,
                                                                     @MParam("终止节点") String toNodeId) throws BaseException {
        return calculatePathLinksByDAlgorithm(netWork, fromNodeId, toNodeId, LayerEnum.FIBER);
    }

    // 获取链路的操作
    public static @NonNull
    List<BasicLink> calculatePathLinksByDAlgorithm(@MParam("当前网络信息") BasicNetWork netWork,
                                                   @MParam("起始节点") String fromNodeId,
                                                   @MParam("终止节点") String toNodeId,
                                                   @MParam("计算的层次") LayerEnum layer) throws BaseException {
       // netWork.checkCurrentNetWork();
        Map<String, String> nodeIdToLinkKey = new HashMap<>();
        Map<String, BasicLink> basicLinkMapByLayer = netWork.getBasicLinkMapByLayer(layer);
        List<String> list = calculatePathByDAlgorithm(netWork, fromNodeId, toNodeId, layer, nodeIdToLinkKey);
        List<BasicLink> res = new ArrayList<BasicLink>();
        if (list.size() > 0) {
            String pre = list.get(0);
            for (int i = 1; i < list.size(); i++) {
                String next = list.get(i);
                String linkId = nodeIdToLinkKey.get(getNodeIdToLinkKey(pre, next));
                res.add(basicLinkMapByLayer.get(linkId));
                pre = next;
            }
        }
        return res;
    }

    // 获取  节点的序列的操作  的操作
    public static List<BasicNode> calculatePathNodesByDAlgorithm(@MParam("当前网络信息") BasicNetWork netWork,
                                                                 @MParam("起始节点") String fromNodeId,
                                                                 @MParam("终止节点") String toNodeId,
                                                                 @MParam("计算的层次") LayerEnum layer) throws BaseException {
        //netWork.checkCurrentNetWork();
        Map<String, String> nodeIdToLinkKey = new HashMap<String, String>();
        List<String> list = calculatePathByDAlgorithm(netWork, fromNodeId, toNodeId, layer, nodeIdToLinkKey);
        List<BasicNode> res = new ArrayList<BasicNode>();
        if (null != list && list.size() > 0) {
            for (String nodeId : list) {
                res.add(netWork.getNodeMap().get(nodeId));
            }
        }
        return res;
    }

    // 计算 最短路径 返回 节点的 ID 序列 list
    public static List<String> calculatePathByDAlgorithm(@MParam("当前网络信息") BasicNetWork netWork,
                                                         @MParam("起始节点") String fromNodeId,
                                                         @MParam("终止节点") String toNodeId,
                                                         @MParam("计算的层次") LayerEnum layer) throws BaseException {
        return calculatePathByDAlgorithm(netWork, fromNodeId, toNodeId, layer, null);
    }

    // 计算最短路径 采用雷雨师兄的D算法
    private static @NonNull
    List<String> calculatePathByDAlgorithm(BasicNetWork netWork,
                                           @MParam("起始节点") String fromNodeId,
                                           @MParam("终止节点") String toNodeId,
                                           @MParam("计算的层次") LayerEnum layer,
                                           @MParam("作为返回值 返回 nodeId map to LinkId")
                                                   Map<String, String> nodeIdToLinkKey) throws BaseException {
        // 校验基本的数据
        //netWork.checkCurrentNetWork();
        Map<String, Integer> keyToIndexMap = new HashMap<String, Integer>();
        Map<Integer, String> indexToKeyMap = new HashMap<Integer, String>();
        // 得到邻接矩阵以对应的关系
        int[][] matrix = getCurrentNetWorkMatrix(netWork, layer, keyToIndexMap, indexToKeyMap, nodeIdToLinkKey);
        Integer head = keyToIndexMap.get(fromNodeId);
        Integer tail = keyToIndexMap.get(toNodeId);
        List<Integer> list = DijkstraAlgorithm.getInstance().routeCalculation(matrix, head, tail);
        List<String> res = new ArrayList<>();
        if (null != list && list.size() > 0) {
            for (Integer index : list) {
                res.add(indexToKeyMap.get(index));
            }
        }
        return res;
    }

    // 获取当前网络的邻接矩阵
    public static int[][] getCurrentFiberNetWorkMatrix(@MParam("当前网络信息") BasicNetWork netWork,
                                                       @MParam("作为返回值 返回nodeId 对应的 index") Map<String, Integer> keyToIndexMap,
                                                       @MParam("作为返回值 返回 index 对应的 nodeId") Map<Integer, String> indexToKeyMap)
            throws BaseException {
        return getCurrentNetWorkMatrix(netWork, LayerEnum.FIBER, keyToIndexMap, indexToKeyMap, null);
    }

    // get key for NodeIdToLinkKey map
    private static String getNodeIdToLinkKey(String fromNodeId, String toNodeId) {
        return fromNodeId + "_" + toNodeId;
    }


    // 根据不同的层次获取网络的信息
    public static int[][] getCurrentNetWorkO1Matrix(@MParam("当前网络信息") BasicNetWork netWork,
                                                    @MParam("返回矩阵的层次") LayerEnum layer,
                                                    @MParam("作为返回值 返回 nodeId 对应的 index") Map<String, Integer> keyToIndexMap,
                                                    @MParam("作为返回值 返回 index 对应的 nodeId ") Map<Integer, String> indexToKeyMap,
                                                    @MParam("作为返回值 返回 nodeId map to LinkId") Map<String, String> nodeIdToLinkKey)
            throws BaseException {
        return getCurrentNetWorkMatrix(netWork, layer, keyToIndexMap, indexToKeyMap, nodeIdToLinkKey, true);
    }


    public static int[][] getCurrentNetWorkMatrix(@MParam("当前网络信息") BasicNetWork netWork,
                                                  @MParam("返回矩阵的层次") LayerEnum layer,
                                                  @MParam("作为返回值 返回 nodeId 对应的 index") Map<String, Integer> keyToIndexMap,
                                                  @MParam("作为返回值 返回 index 对应的 nodeId ") Map<Integer, String> indexToKeyMap,
                                                  @MParam("作为返回值 返回 nodeId map to LinkId") Map<String, String> nodeIdToLinkKey)
            throws BaseException {
        return getCurrentNetWorkMatrix(netWork, layer, keyToIndexMap, indexToKeyMap, nodeIdToLinkKey, false);
    }

    // 根据不同的层次获取网络的信息
    public static int[][] getCurrentNetWorkMatrix(@MParam("当前网络信息") BasicNetWork netWork,
                                                  @MParam("返回矩阵的层次") LayerEnum layer,
                                                  @MParam("作为返回值 返回 nodeId 对应的 index") Map<String, Integer> keyToIndexMap,
                                                  @MParam("作为返回值 返回 index 对应的 nodeId ") Map<Integer, String> indexToKeyMap,
                                                  @MParam("作为返回值 返回 nodeId map to LinkId") Map<String, String> nodeIdToLinkKey,
                                                  @MParam("是否是 01 矩阵") boolean is01Matrix)
            throws BaseException {
        // 校验基本的数据
        LocalVerify.verifyObject(keyToIndexMap, "keyToIndexMap");
        LocalVerify.verifyObject(indexToKeyMap, "indexToKeyMap");
        LocalVerify.verifyObject(layer, "layer");
        // 校验网络的信息
       // netWork.checkCurrentNetWork();
        // 获取到链路
        List<BasicLink> basicLinks = netWork.getBasicLinksByLayer(layer);
        /*  下面是构建数组的操作  */
        int[][] res = null;

        List<BasicNode> nodeList = netWork.getNodeList();

        // 修改是否有效的操作
        if (null != nodeList && nodeList.size() > 0) {
            // 去掉没有意义的数据
            nodeList = nodeList.stream()
                    .filter(node -> node.getFlag().equals(Status.USING.getFlag())).collect(Collectors.toList());
            int n = nodeList.size();
            for (int i = 0; i < n; i++) {
                keyToIndexMap.put(nodeList.get(i).getNodeId(), i);
                indexToKeyMap.put(i, nodeList.get(i).getNodeId());
            }
            res = new int[n][n];
            if (!is01Matrix) {// 如果不是01 矩阵的时候的情形
                for (int[] re : res) {
                    Arrays.fill(re, Integer.MAX_VALUE);
                }
            }
            if (null != basicLinks && basicLinks.size() > 0) {
                // 过去掉其他的 仅仅包含有效的链路
                basicLinks = basicLinks.stream()
                        .filter(link -> link.getFlag().equals(Status.USING.getFlag())).collect(Collectors.toList());
                // 形成链路矩阵
                for (BasicLink link : basicLinks) {
                    Integer head = keyToIndexMap.get(link.getNodeHead());
                    Integer tail = keyToIndexMap.get(link.getNodeTail());
                    if (null != nodeIdToLinkKey) {
                        // nodeId map to LinkId
                        nodeIdToLinkKey.put(getNodeIdToLinkKey(link.getNodeHead(), link.getNodeTail()), link.getId());
                        // nodeId map to LinkId
                        nodeIdToLinkKey.put(getNodeIdToLinkKey(link.getNodeTail(), link.getNodeHead()), link.getId());
                    }
                    res[head][tail] = 1;
                    res[tail][head] = 1;
                }
            }
        }
        return res;
    }

    //景涛新增，获取承载层的链路组
    public static List<BasicLink> findPathLinks(List<BasicLink> links, List<BasicNode> nodes, Map<String, BasicNode> nodeMap,
                                                BasicNode source, BasicNode destination, double rate) {
        Map<BasicNode, Integer> nodeIntegerMap = new HashMap<>();//节点坐标字典
        int size = nodes.size();//矩阵大小
        long[][] adjacentMatrix = new long[size][size];//图矩阵
        int ori = 0;//起点
        int des = 0;//终点
        //寻找起点和终点的引用，并确定节点的坐标字典
        for (int i = 0; i < size; i++) {
            if (nodes.get(i).equals(source)) {
                ori = i;
            }
            if (nodes.get(i).equals(destination)) {
                des = i;
            }
            nodeIntegerMap.put(nodes.get(i), i);
        }
        //初始化矩阵
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i == j) {
                    adjacentMatrix[i][j] = 0;
                } else {
                    adjacentMatrix[i][j] = Long.MAX_VALUE;
                }
            }
        }
        //设置矩阵
        for (BasicLink link : links) {
            BasicNode fromNode = nodeMap.get(link.getNodeHead());
            BasicNode toNode = nodeMap.get(link.getNodeTail());
            //现在fiberLink结构无带宽
            //if (rate <= link.getRate()) {
            long len = 10;
            if (link.getLength() != null) {
                len = link.getLength();
            }
            adjacentMatrix[nodeIntegerMap.get(toNode)][nodeIntegerMap.get(fromNode)] = len * 1000;
            adjacentMatrix[nodeIntegerMap.get(fromNode)][nodeIntegerMap.get(toNode)] = len * 1000;
            //}
        }
        //算路
        List<Integer> route = routeCalculation(adjacentMatrix, ori, des);
        //生成路由
        List<BasicLink> returnLink = new ArrayList<>();
        for (int i = 0; i < route.size() - 1; i++) {
            BasicNode from = nodes.get(route.get(i));
            BasicNode to = nodes.get(route.get(i + 1));
            for (BasicLink link : links) {
                if ((link.getNodeHead().equals(from.getNodeId()) && link.getNodeTail().equals(to.getNodeId())) ||
                        (link.getNodeHead().equals(to.getNodeId()) && link.getNodeTail().equals(from.getNodeId()))) {
                    returnLink.add(link);
                    break;
                }
            }
        }
        return returnLink;
    }

    private static @NonNull
    List<Integer> routeCalculation(long[][] adjacentMatrix, int origin, int destination) {
        int size = adjacentMatrix[1].length;//获取邻接矩阵大小
        long[] distance = new long[size];//最短路长度
        boolean[] flag = new boolean[size];//标记i顶点最短路有无找到
        int[] prev = new int[size];//前驱数组
        ArrayList<Integer> route = new ArrayList<Integer>();//路由数组
        //初始化
        for (int i = 0; i < size; i++) {
            distance[i] = adjacentMatrix[origin][i];//初始化距离都为起点到各个点的权值
            flag[i] = false;//起点到各个点的最短路径还没获取到
            if (distance[i] < Long.MAX_VALUE && distance[i] != 0) prev[i] = origin;
            else prev[i] = -1;//各个顶点的前驱点为-1
        }
        //对起点进行初始化
        flag[origin] = true;
        distance[origin] = 0;//起点到起点的距离为0
        //遍历邻接矩阵size次；每次找出一个顶点的最短路径
        int now = origin;
        int before;
        for (int i = 0; i < size; i++) {
            before = now;
            //寻找当前的最短路径
            //即在为获取最短路径的顶点中，找到离起点最近的顶点（k）
            long min = Long.MAX_VALUE;
            for (int j = 0; j < size; j++) {
                if (flag[j] == false && distance[j] < min) {
                    min = distance[j];
                    now = j;
                }
            }
            if (now == before) break;//没有新节点的情况
            //标记"节点now"为已经获取到最短路径
            flag[now] = true;
            //修正当前最短路径和前驱节点
            for (int j = 0; j < size; j++) {
                if (flag[j] == true) continue;
                long tmp = (adjacentMatrix[now][j] == Long.MAX_VALUE ? Long.MAX_VALUE : (min + adjacentMatrix[now][j]));
                if (tmp < distance[j]) {
                    distance[j] = tmp;
                    prev[j] = now;
                }
            }
        }
        //获取路由数组
        Stack<Integer> stack = new Stack<Integer>();
        int topPtr = destination;
        if (prev[topPtr] == -1) return route;
        stack.push(topPtr);
        while (topPtr != origin) {
            topPtr = prev[topPtr];
            stack.push(topPtr);
        }
        while (!stack.empty()) {
            route.add(stack.pop());
        }
        return route;
    }
}
